package com.mlamp.二叉树;

import java.util.HashMap;

public class 判断二叉树的两个节点是否是堂兄弟 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);

        判断二叉树的两个节点是否是堂兄弟 instance = new 判断二叉树的两个节点是否是堂兄弟();
        boolean cousins = instance.isCousins(root, 3, 4);
        System.out.println(cousins);

        cousins = instance.isCousins(root, 2, 3);
        System.out.println(cousins);


    }

    /**
     * 判断给定的x，y是否是堂兄弟节点
     *
     * @param root
     * @param x
     * @param y
     * @return
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        HashMap<Integer, Integer> depth = new HashMap<>();
        HashMap<Integer, TreeNode> parent = new HashMap<>();
        TreeNode pre = null;
        dfs(root, depth, parent, pre);
        return depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y);

    }

    public void dfs(TreeNode root, HashMap<Integer, Integer> depth, HashMap<Integer, TreeNode> parent, TreeNode pre) {
        if (root != null) {
            if (pre == null) {
                depth.put(root.value, 0);
            } else {
                depth.put(root.value, depth.get(pre.value) + 1);
            }
            parent.put(root.value, pre);
            dfs(root.left, depth, parent, root);
            dfs(root.right, depth, parent, root);
        }
    }


    public static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }


}
